#include <stdio.h>
#include <iostream>
#include <assert.h>
#include <vector>
using namespace std;


void merge(int a[], int lo, int mi, int hi){
	int lb = mi - lo;
	vector<int> b(lb);
	for (int i = lo, j = 0; i < mi; i++, j++) b[j] = a[i];
	for (int ia = lo, ib = 0, ic = mi; (ib < lb || ic < hi);){
		if ((ib < lb) && (!(ic < hi) || (b[ib] <= a[ic]))) a[ia++] = b[ib++];
		if ((ic < hi) && (!(ib < lb) || (a[ic] < b[ib]))) a[ia++] = a[ic++];
	}
}

void mergeSort(int a[], int lo, int hi){
	if (hi - lo < 2) return;
	int mi = (hi + lo) >> 1;
	mergeSort(a, lo, mi);
	mergeSort(a, mi, hi);
	merge(a, lo, mi, hi);
}

int main(){
	int a[] = { 1, 2, 6, 4, 5, 7, 8, 43, 23, 45, 4 };
	int n = sizeof(a) / sizeof(*a);
	mergeSort(a, 0, n);
	for (int i = 0; i < n; i++){
		cout << a[i] << " ";
	}
	cout << endl;
	return 0;
}

